#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define M 500 + 5
#define inf 0x3f3f3f3f
using namespace std;
int tot = 1, h[M], vs[M], vt[M], v[M], d[M], cur[M], n, m;
struct edge
{
	int from, to, cap, flow, ne;
} E[200005];
void Addedge(int from, int to, int cap)
{
	E[++tot] = (edge){from, to, cap, 0, h[from]};
	h[from] = tot;
	E[++tot] = (edge){to, from, 0, 0, h[to]};
	h[to] = tot;
}
bool bfs()
{
	queue<int> q;
	for (int i = 0; i < n; i++)
		v[i] = 0;
	v[0] = 1;
	d[0] = 0;
	q.push(0);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = h[x]; i; i = E[i].ne)
		{
			edge e = E[i];
			if (!v[e.to] && e.cap > e.flow)
			{
				v[e.to] = 1;
				d[e.to] = d[x] + 1;
				q.push(e.to);
			}
		}
	}
	return v[n - 1];
}
int dfs(int x, int a)
{
	if (x == n - 1 || !a)
		return a;
	int flow = 0;
	for (int &i = cur[x]; i; i = E[i].ne)
	{
		edge &e = E[i];
		if (d[e.to] != d[x] + 1)
			continue;
		int f = dfs(e.to, min(a, e.cap - e.flow));
		if (f)
		{
			a -= f;
			e.flow += f;
			E[i ^ 1].flow -= f;
			flow += f;
			if (!a)
				break;
		}
	}
	return flow;
}
void dinic()
{
	int flow = 0;
	while (bfs())
	{
		for (int i = 0; i < n; i++)
			cur[i] = h[i];
		flow += dfs(0, inf);
	}
}
void dfs_s(int x)
{
	for (int i = h[x]; i; i = E[i].ne)
	{
		if (i & 1)
			continue;
		edge e = E[i];
		if (e.cap > e.flow && !vs[e.to])
		{
			vs[e.to] = 1;
			dfs_s(e.to);
		}
	}
}
void dfs_t(int x)
{
	for (int i = h[x]; i; i = E[i].ne)
	{
		if ((i & 1) == 0)
			continue;
		edge e = E[i ^ 1];
		if (e.cap > e.flow && !vt[e.from])
		{
			vt[e.from] = 1;
			dfs_t(e.from);
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		Addedge(x, y, c);
	}
	dinic();
	vs[0] = 1, vt[n - 1] = 1;
	dfs_s(0);
	dfs_t(n - 1);
	int cnt = 0;
	for (int i = 2; i <= tot; i += 2)
		if (E[i].flow == E[i].cap && vs[E[i].from] && vt[E[i].to])
			cnt++;
	printf("%d\n", cnt);
	return 0;
}